class Solution {
public:
    void get_sum(vector<int>& candidates, int target, int start, vector<int> per_ans, vector<vector<int>>& ans){
        if(target == 0){
            ans.push_back(per_ans);
            return;
        }

        for(int i=start; i<candidates.size(); i++){
            if(candidates[i] > target) return;
            per_ans.push_back(candidates[i]);
            get_sum(candidates, target-candidates[i], i, per_ans, ans);
            per_ans.pop_back();
        }

    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
        vector<vector<int>> ans;
        vector<int> per_ans;
        int n = candidates.size();
        if(n == 1 && (target%candidates[0] != 0)){
            return ans;
        }

        sort(candidates.begin(), candidates.end());

        for(int i=0; i<n; i++){
            per_ans.push_back(candidates[i]);
            get_sum(candidates, target-candidates[i], i, per_ans, ans);
            per_ans.pop_back();
        }

        return ans;
    }
};